1. Field of Use
The present invention relates generally to multiprocessor systems and, more particularly, to deadlock detection apparatus for avoiding deadly embrace situations between the processing units within a multiprocessing system.
2. Prior Art
In computer systems, it is important that resources be allocated in a way that deadlock does not occur. A deadlock occurs when processes holding some resources request access to resources held by other processes in the same set. Unless the deadlock is resolved, all the processes involved are blocked indefinitely. Therefore, a deadlock requires the attention of a process outside those involved in the deadlock for its detection and resolution.
Generally, a deadlock can be resolved by aborting one or more processes involved in the deadlock and granting the released resources to other processes involved in the deadlock. A process is aborted by withdrawing all its resource requests, restoring its state to an appropriate previous state, relinquishing all the resources it acquired after that state, and restoring all the relinquished resources to their original states.
U.S. Pat. No. 4,318,182 discloses a system in which a deadlock detection mechanism detects situations where two or more processes are waiting for related events which cannot happen, preventing a requesting process from waiting for the availability of a resource or resources which are already held by a second process which is waiting directly or indirectly upon the first process. This requires that the system have access to all of the resources within the system to ensure that a requested resource is not currently assigned to a second process which is already waiting directly or indirectly for a second resource currently assigned to a first process.
In tightly coupled multiprocessor systems, the different processors are required to share data within a common or global main memory system. To preclude race conditions and the occurrence of the deadlock or deadly embrace situation, it is well known to have each processor use test and set lock instructions. That is, each processor obtains or tests the lock for a shared data structure or section of main memory. If it is unlocked, the processor gets the lock and accesses the segment. However, if the segment is locked, the processor spins in a loop, periodically testing until the lock becomes available.
While the above type of mutually exclusive protocol has been effective in eliminating the above problems, this approach may not be effective in certain types of situations which may not be easily detected. For example, this type of situation may go undetected in a multiprocessor system which includes processors with local memories where the local memories of such processors are required to be shared by other processors of the system.
Accordingly, it is a primary object of the present invention to provide a multiprocessor lock mechanism which reliably protects against deadlocks.
It is a more specific object of the present invention to provide a multiprocessor lock protocol which permits reliable accesses to all processor shared memories within a tightly coupled multiprocessor system.